home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / debugger / ddd-1.000 / ddd-1 / ddd-1.4b / ddd / Map.h < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-21  |  6.4 KB  |  286 lines
  1. // $Id: Map.h,v 1.3 1995/11/21 13:50:38 zeller Exp $
  2. // Map template
  3.  
  4. // Copyright (C) 1995 Technische Universitaet Braunschweig, Germany.
  5. // Written by Dorothea Luetkehaus (luetke@ips.cs.tu-bs.de).
  6. // 
  7. // This file is part of the DDD Library.
  8. // 
  9. // The DDD Library is free software; you can redistribute it and/or
  10. // modify it under the terms of the GNU Library General Public
  11. // License as published by the Free Software Foundation; either
  12. // version 2 of the License, or (at your option) any later version.
  13. // 
  14. // The DDD Library is distributed in the hope that it will be useful,
  15. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  17. // See the GNU Library General Public License for more details.
  18. // 
  19. // You should have received a copy of the GNU Library General Public
  20. // License along with the DDD Library -- see the file COPYING.LIB.
  21. // If not, write to the Free Software Foundation, Inc.,
  22. // 675 Mass Ave, Cambridge, MA 02139, USA.
  23. // 
  24. // DDD is the data display debugger.
  25. // For details, see the DDD World-Wide-Web page, 
  26. // `http://www.cs.tu-bs.de/softech/ddd/',
  27. // or send a mail to the DDD developers at `ddd@ips.cs.tu-bs.de'.
  28.  
  29. //-----------------------------------------------------------------------------
  30. // Template fuer eine Map.
  31. // Key sollte nicht 0 sein, da dies fuer first() und next() besondere
  32. // Bedeutung hat. Ausserdem muss '==' fuer Key definiert sein.
  33. //-----------------------------------------------------------------------------
  34.  
  35. //-----------------------------------------------------------------------------
  36. #ifndef _Map_h
  37. #define _Map_h
  38.  
  39. #if defined(__GNUC_MINOR__) && (__GNUC_MINOR__ >= 5)
  40. #pragma interface
  41. #endif
  42.  
  43. #include "assert.h"
  44.  
  45. typedef void* MapRef;
  46.  
  47. template <class Key, class Contents>
  48. class Map {
  49.     int _length;
  50. public:
  51.     // leere Map erzeugen
  52.     Map ();
  53.     
  54.     // leert die Map
  55.     void clear ();
  56.  
  57.     // leert die Map, und ruft delete fuer alle Contents-Pointer auf
  58.     void delete_all_contents ();
  59.     
  60.     // Destructor (Map vorher leeren)
  61.     ~Map() { clear(); }
  62.     
  63.     // einfuegen bzw ueberschreiben; 0 bei c == 0 (kein Einfuegen)
  64.     int insert (Key k, Contents* c);
  65.     
  66.     // loeschen, falls vorhanden
  67.     void del (Key k);
  68.  
  69.  
  70.     // falls nicht vorhanden 0 zurueckgeben
  71.     Contents* get (Key k) const;
  72.     
  73.     // 1, wenn enthalten, sonst 0
  74.     int contains (Key k) const;
  75.     
  76.     // 0, falls nicht vorhanden, sonst bel. enth. Key
  77.     // simuliert 0-terminierte Liste
  78.     Key first_key(MapRef& ln) const;
  79.     static Key next_key(MapRef& ln);
  80.     
  81.     Contents* first(MapRef& ln) const;
  82.     static Contents* next(MapRef& ln);
  83.     
  84.     inline int length()  const { return _length; }
  85.  
  86. private:
  87.     //Realisierung als Liste;
  88.     struct ListNode {
  89.     Key key;
  90.     Contents* cont;
  91.     ListNode* _next;
  92.     };
  93.     
  94.     ListNode* _first;
  95.     
  96.     ListNode* search (Key k) const {
  97.     // falls nicht vorhanden 0 zurueckgeben
  98.     ListNode* ln;
  99.     
  100.     ln = _first;
  101.     while (ln != 0 && !(ln->key == k)) 
  102.         ln = ln->_next;
  103.     return ln;
  104.     }
  105. };
  106.  
  107.  
  108.  
  109. template <class Key, class Contents>
  110. Map<Key,Contents>::Map () : _length(0), _first(0) {}
  111. //-----------------===---------------
  112.  
  113.  
  114. template <class Key, class Contents>
  115. void Map<Key, Contents>::clear() {
  116. //-----------------------=====-------
  117.     // leert die Map
  118.     ListNode* ln;
  119.     ListNode* prev;
  120.  
  121.     ln = _first;
  122.     while (ln != 0) {
  123.     prev = ln;
  124.     ln = ln->_next;
  125.     delete prev;
  126.     }
  127.     _first = 0;
  128.     _length = 0;
  129. }
  130.  
  131.  
  132. template <class Key, class Contents>
  133. void Map<Key, Contents>::delete_all_contents() {
  134. //-----------------------===================-------
  135.     // leert die Map und ruft delete fuer alle Contents-Pointer
  136.     ListNode* ln;
  137.     ListNode* prev;
  138.  
  139.     ln = _first;
  140.     while (ln != 0) {
  141.     prev = ln;
  142.     ln = ln->_next;
  143.     delete prev->cont;
  144.     delete prev;
  145.     }
  146.     _first = 0;
  147.     _length = 0;
  148. }
  149.  
  150.  
  151. template <class Key, class Contents>
  152. int Map<Key, Contents>::insert (Key k, Contents* c) {
  153. //----------------------======------
  154.     if (c == 0) // nichts leeres einfuegen
  155.     return 0;
  156.  
  157.     // einfuegen bzw ueberschreiben
  158.     ListNode* ln = search (k);
  159.     if (ln == 0) {
  160.  
  161.     ln = new ListNode;
  162.     ln->key = k;
  163.     ln->cont = c;
  164.  
  165.     ln->_next = _first;
  166.     _first = ln;
  167.     _length++;
  168.     }
  169.     else {
  170.     ln->cont = c;
  171.     }
  172.     return 1;
  173. }
  174.  
  175. template <class Key, class Contents>
  176. void Map<Key, Contents>::del (Key k) {
  177. //-----------------------===---------
  178.     // loeschen, falls vorhanden
  179.     if (_first == 0)
  180.     return;
  181.     
  182.     ListNode* prev = 0;
  183.     ListNode* ln = _first;
  184.     
  185.     while (ln != 0 && !(ln->key == k)) {
  186.     prev = ln;
  187.     ln = ln->_next;
  188.     }
  189.  
  190.     if (ln == 0)
  191.     return; // nicht gefunden
  192.                
  193.     if (prev == 0) {
  194.     // erstes Element loeschen
  195.     assert (_first == ln);
  196.     _first = _first->_next;
  197.     delete ln;
  198.     _length--;
  199.     }
  200.     else {
  201.     prev->_next = ln->_next;
  202.     delete ln;
  203.     _length--;
  204.     }
  205.     assert (!contains(k));
  206. }
  207.  
  208. template <class Key, class Contents>
  209. Contents* Map<Key, Contents>::get (Key k) const {
  210. //----------------------------===----
  211.     // falls nicht vorhanden 0 zurueckgeben
  212.     ListNode* ln = search (k);
  213.     if (ln == 0)
  214.     return 0;
  215.     else 
  216.     return ln->cont;
  217. }
  218.  
  219. template <class Key, class Contents>
  220. int Map<Key, Contents>::contains (Key k) const {
  221. //----------------------========-----
  222.     // 1, wenn enthalten, sonst 0
  223.     return (search (k) != 0);
  224. }
  225.  
  226. template <class Key, class Contents>
  227. Key Map<Key, Contents>::first_key(MapRef& ref) const {
  228. //----------------------=========----
  229.     // 0, falls leer, sonst _first
  230.     if (_first == 0) {
  231.     ref = 0;
  232.     return 0;
  233.     }
  234.     else {
  235.     ref = _first->_next;
  236.     return _first->key;
  237.     }
  238. }
  239.  
  240. template <class Key, class Contents>
  241. Key Map<Key, Contents>::next_key(MapRef& ref) {
  242. //----------------------========-----
  243.     // durchlaeuft 0-terminierte Liste
  244.     if (ref == 0 ) {
  245.     //am Ende angelangt
  246.     return 0;
  247.     }
  248.     else {
  249.     ListNode* current_ln = (ListNode *) ref;
  250.     ref = current_ln->_next;
  251.     return current_ln->key;
  252.     }
  253. }
  254.  
  255.  
  256. template <class Key, class Contents>
  257. Contents* Map<Key, Contents>::first(MapRef& ref) const {
  258. //----------------------------=====--------
  259.     // 0, falls leer, sonst _first
  260.     if (_first == 0) {
  261.     ref = 0;
  262.     return 0;
  263.     }
  264.     else {
  265.     ref = _first->_next;
  266.     return _first->cont;
  267.     }
  268. }
  269.  
  270. template <class Key, class Contents>
  271. Contents* Map<Key, Contents>::next(MapRef& ref) {
  272. //----------------------------====---------
  273.     // durchlaeuft 0-terminierte Liste
  274.     if (ref == 0 ) {
  275.     //am Ende angelangt
  276.     return 0;
  277.     }
  278.     else {
  279.     ListNode* current_ln = (ListNode *) ref;
  280.     ref = current_ln->_next;
  281.     return current_ln->cont;
  282.     }
  283. }
  284.  
  285. #endif
  286.